package com.rayboo.example.algorithm.sort;

import com.rayboo.example.util.ArrayUtils;

import java.util.Arrays;

/**
 * 快速排序 （是一种交换排序）
 *
 * @author ray
 * @since 2019/08/01
 *
 * <p>1、从数列中挑出一个元素，称为 "基准"
 * 2、重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
 * 在这个分割之后，该基准是它的最后位置。这个称为分割操作。
 * 3、递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。
 *
 * <p>https://cloud.tencent.com/developer/article/1403566
 * <p>https://www.runoob.com/w3cnote/quick-sort-2.html
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] arr = ArrayUtils.randomNoRepeatIntArray(0, 100, 12);
        System.out.println("排序前：\n" + Arrays.toString(arr));

        new QuickSort().sort(arr);
        System.out.println("排序后：\n" + Arrays.toString(arr));

        System.out.println("遍历：  ");
        Arrays.stream(arr).forEach(System.out::println);
    }

    /**
     * 排序
     *
     * @param sourceArray 源数组
     */
    public void sort(int[] sourceArray) {
        quickSort(sourceArray, 0, sourceArray.length - 1);
    }

    /**
     * 快速排序
     *
     * @param arr  数组
     * @param low  基准位置
     * @param high 最大索引
     */
    public static int[] quickSort(int[] arr, int low, int high) {
        int left, right, base, temp;

        if (low > high || arr == null || arr.length <= 1) return arr;

        // 以最左边的数(left)为基准
        left = low;
        right = high;
        //temp就是基准位
        base = arr[low];

        while (left < right) {
            // 从序列右端开始，向左遍历(依次往左递减)，直到找到小于base的数
            while (base <= arr[right] && left < right) {
                right--;
            }
            // 从序列左端开始，向右遍历(依次往右递增)，直到找到大于base的数
            while (base >= arr[left] && left < right) {
                left++;
            }
            //如果满足条件则交换
            if (left < right) {
                temp = arr[right];
                arr[right] = arr[left];
                arr[left] = temp;
            }

        }
        //最后将基准为与i和j相等位置的数字交换
        arr[low] = arr[left];
        // 最后将base放到left位置。此时，left位置的左侧数值应该都比left小；而left位置的右侧数值应该都比left大。
        arr[left] = base;

        //递归调用左半数组
        quickSort(arr, low, right - 1);
        //递归调用右半数组
        quickSort(arr, right + 1, high);

        return arr;
    }

}
